#include "BTreeNode.h"

using namespace std;

const int LASTKEY = (1024/(sizeof(Recidkeypair)));
const int PLASTKEY = (1024/(sizeof(Pageidkeypair)) - 1);

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
BTLeafNode::BTLeafNode()
{
	int *buf = (int*)buffer;
	memset(buf,-1,1024);
}

RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	if(pid < 0)
		return RC_INVALID_PID;
	RC rc;
	rc = pf.read(pid,buffer);
	if(rc < 0)
		return rc;


	return 0; }
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	if(pid < 0)
		return RC_INVALID_PID;
	RC rc;
	rc = pf.write(pid,buffer);
	if(rc < 0)
		return rc;
	
	return 0; }

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	Recidkeypair entry;
	int cnt = 0;
	Recidkeypair *buf = (Recidkeypair*)buffer;
	for(int i = 0; i < LASTKEY; i++)
	{
		entry = buf[i];
		if(entry.key == -1)
			break;
		cnt++;
	}
	return cnt; }

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	if(rid.pid < 0 || rid.sid < 0)
		return RC_INVALID_RID;
	Recidkeypair entry;
	entry.key = key;
	entry.record = rid;
	Recidkeypair *buf = (Recidkeypair*)buffer;
	int keycnt = getKeyCount();
	int i;
	if(keycnt == LASTKEY)
		return RC_NODE_FULL;
	else
	{
		for(i = 0; i < keycnt; i++)
		{
			if(entry.key < buf[i].key)
				break;
		}
		for(int j=keycnt ; j > i; j--)
		{
			buf[j] = buf[j-1];
		}
		buf[i] = entry;
	}
	return 0; }

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	if(rid.pid < 0 || rid.sid < 0)
		return RC_INVALID_RID;
	Recidkeypair entry;
	entry.key = key;
	entry.record = rid;
	int i;
	char* tempbuf;
	tempbuf = (char*)malloc(1024+sizeof(Recidkeypair));
	memset(tempbuf,-1,1028);;
	memcpy(tempbuf,buffer,1024);
	Recidkeypair *buf = (Recidkeypair*)tempbuf;
	for(i = 0; i < getKeyCount(); i++)
	{
		if(entry.key < buf[i].key)
			break;
	}
	if(i != getKeyCount())
		memmove(buf+i+1,buf+i,1024-i*sizeof(Recidkeypair)); 
	buf[i] = entry;
	i = (getKeyCount()+1)/2;
	Recidkeypair *sibbuf = (Recidkeypair*)sibling.buffer;
	siblingKey = buf[i].key;
	memcpy(sibbuf,buf+i,1032-i*sizeof(Recidkeypair));
	memset(buffer,-1,1020);
	memcpy(buffer,buf,(i*sizeof(Recidkeypair)));
	free(tempbuf);
	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int i;
	Recidkeypair entry;
	Recidkeypair *buf = (Recidkeypair*)buffer;
	for(i = 0; i < getKeyCount(); i++)
	{
		entry = buf[i];
		if(entry.key >= searchKey)
			break;
	}
	if (i != getKeyCount())
	{
		eid = i;
		return 0; 
	}
	else
		return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	if( eid < 0 || eid >= getKeyCount())
		return RC_INVALID_CURSOR;
	Recidkeypair entry;
	Recidkeypair *buf = (Recidkeypair*)buffer;
	entry = buf[eid];
	key = entry.key;
	rid = entry.record;
	return 0; }

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	int *buf = (int*)buffer;
	PageId ptr = buf[(1024/sizeof(int))-1];
	return ptr; }

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	int *buf = (int*)buffer;
	buf[(1024/sizeof(int))-1] = pid;
	return 0; 
}


BTNonLeafNode::BTNonLeafNode()
{
	memset(buffer,-1,1024);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	if(pid < 0 || pid >= pf.endPid())
		return RC_INVALID_PID;
	RC rc;
	rc = pf.read(pid,buffer);
	if(rc < 0)
		return rc;
	return 0; }
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	if(pid < 0)
		return RC_INVALID_PID;
	RC rc;
	rc = pf.write(pid,buffer);
	if(rc < 0)
		return rc;
	return 0; }

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	Pageidkeypair entry;
	int cnt = 0;
	Pageidkeypair *buf = (Pageidkeypair*)buffer;
	for(int i = 0; i < PLASTKEY; i++)
	{
		entry = buf[i];
		if(entry.key == -1)
			break;
		cnt++;
	}
	return cnt;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	if(pid < 0)
		return RC_INVALID_PID;
	Pagekeyidpair entry;
	entry.key = key;
	entry.page = pid;
	int i;
	char *tempbuf;
	tempbuf = (char*)malloc(1020);
	memcpy(tempbuf,buffer+sizeof(int),1020);
	Pagekeyidpair *buf = (Pagekeyidpair*)tempbuf;
	int keycnt = getKeyCount();
	if(keycnt == PLASTKEY)
	{
		free(tempbuf);
		return RC_NODE_FULL;
	}
	else
	{
		for(i = 0; i < keycnt; i++)
		{
			if(entry.key < buf[i].key)
				break;
		}
		for(int j=keycnt ; j > i; j--)
		{
			buf[j] = buf[j-1];
		}
		buf[i] = entry;
		memcpy(buffer+sizeof(int),tempbuf,1020);
		free(tempbuf);
	}


	return 0;
}


/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	if(pid < 0)
		return RC_INVALID_PID;
	Pagekeyidpair entry;
	entry.key = key;
	entry.page = pid;
	int i;
	char* tempbuf;
	tempbuf = (char*)malloc(1020+sizeof(Pagekeyidpair));
	memset(tempbuf,-1,1028);
	memcpy(tempbuf,buffer+sizeof(int),1020);
	Pagekeyidpair *buf = (Pagekeyidpair*)tempbuf;
	for(i = 0; i < getKeyCount(); i++)
	{
		if(entry.key < buf[i].key)
			break;
	}
	if(i != getKeyCount())
		memmove(buf+i+1,buf+i,(PLASTKEY-i)*sizeof(Pageidkeypair)); 
	buf[i] = entry;
	char *tempbuf1;
	tempbuf1 = (char*)malloc(1024+sizeof(Pagekeyidpair));
	memset(tempbuf1,-1,1032);
	memcpy(tempbuf1,buffer,1024);
	memcpy(tempbuf1+sizeof(int),tempbuf,1020+sizeof(Pagekeyidpair));
	Pageidkeypair *buf1 = (Pageidkeypair*)tempbuf1;
	i = (getKeyCount()+1)/2;
	midKey = buf1[i].key;
	memcpy(sibling.buffer,tempbuf1+i*sizeof(Pageidkeypair)+sizeof(Pageidkeypair),1032-i*sizeof(Pageidkeypair)-sizeof(Pageidkeypair));
	memset(buffer,-1,1024);
	memcpy(buffer,buf1,(i*sizeof(Pageidkeypair)+sizeof(int)));
	free(tempbuf);
	free(tempbuf1);
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int i;
	Pageidkeypair entry;
	Pageidkeypair *buf = (Pageidkeypair*)buffer;
	int k = getKeyCount();
	for(i = 0; i < k; i++)
	{
		entry = buf[i];
		if(entry.key > searchKey || entry.key==-1)
			break;
	}
	pid = buf[i].page;
	return 0; 
}


/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	RC rc;
	int *buf = (int*)buffer;
	buf[0] = pid1;
	rc = insert(key,pid2);
	return rc; }

RC BTNonLeafNode::setRootPid(PageId pid)
{ 
	int *buf = (int*)buffer;
	buf[0] = pid;
	return 0; 
}

PageId BTNonLeafNode::getRootPid()
{ 
	int *buf = (int*)buffer;
	PageId ptr = buf[0];
	return ptr; 
}

RC BTNonLeafNode::setTreeHeight(int height)
{ 
	int *buf = (int*)buffer;
	buf[1] = height;
	return 0; 
}

int BTNonLeafNode::getTreeHeight()
{ 
	int *buf = (int*)buffer;
	int ptr = buf[1];
	return ptr; 
}
